package com.ruoyi.learn.java.algorithm.graph;

import java.util.*;

public class DFS {

    // 存储图的邻接表
    private Map<Integer, List<Integer>> graph;
    // 记录节点是否被访问过
    private Set<Integer> visited;

    public DFS() {
        graph = new HashMap<>();
        visited = new HashSet<>();
    }

    // 添加边（无向图）
    public void addEdge(int u, int v) {
        graph.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
        graph.computeIfAbsent(v, k -> new ArrayList<>()).add(u);
    }

    // 深度优先搜索（递归）
    public void dfsRecursive(int node) {
        // 标记当前节点为已访问
        visited.add(node);
        System.out.print(node + " ");

        // 遍历所有相邻节点
        for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                dfsRecursive(neighbor);
            }
        }
    }

    // 重置访问状态（用于多次调用）
    public void resetVisited() {
        visited.clear();
    }

    // 主函数测试
    public static void main(String[] args) {
        DFS dfs = new DFS();

        // 构建图：     1
        //            / \
        //           2   3
        //          /   / \
        //         4   5   6

        dfs.addEdge(1, 2);
        dfs.addEdge(1, 3);
        dfs.addEdge(2, 4);
        dfs.addEdge(3, 5);
        dfs.addEdge(3, 6);

        System.out.println("递归 DFS 遍历结果：");
        dfs.dfsRecursive(1); // 从节点 1 开始
        System.out.println();
    }
}
